package com.SuanFa.test;

import org.junit.Test;

import java.util.Arrays;

//二分查找
public class ErFen_1 {
    public static void main(String[] args) {
        int[] a = {7, 13, 21, 30, 38, 44, 52, 53};
        int i = binarySearchBasic(a, 7);
        System.out.println(i);
        int b = binarySearchBasic1(a, 7);
    }

    public static int binarySearchBasic(int[] a, int target) {
        int i = 0;
        int j = a.length - 1;
        while (i <= j) {
            int m = (i + j) >>> 1;//使用符号右移运算
            if (a[m] == target) {
                return m;
            } else if (a[m] > target) {
                j = m - 1;
            } else {
                i = m + 1;
            }
        }
        return -1;
    }

    @Test
    public void test() {
        int i = 0;
        int j = Integer.MAX_VALUE - 1;
        int m = (i + j) / 2;
        i = m + 1;
        System.out.println(i);
        System.out.println(j);
        System.out.println(i + j);
        m = (i + j) >>> 1;
        System.out.println(m);
    }

    public static int binarySearchBasic1(int[] a, int target) {
        int i = 0, j = a.length;
        while (1 < j - i) {
            int m = (i + j) >>> 1;
            if (target < a[m]) {
                j = m;
            } else {
                i = m;
            }
        }
        if (a[i] == target) {
            return i;
        } else {
            return -1;
        }
    }

    @Test
    public void test1() {
        int[] a = {2, 5, 8};
        int target = 9;
        //得到数字再数组中的位置索引
        int i = Arrays.binarySearch(a, 5);
        System.out.println(i);
        int b = Arrays.binarySearch(a, 4);
        System.out.println(b);
        //将数字插入到数组中
        int insertindex = Math.abs(b + 1);
        int[] m = new int[a.length + 1];
        System.arraycopy(a, 0, m, 0, insertindex);
        m[insertindex] = 4;
        System.arraycopy(a, insertindex, m, insertindex + 1, a.length - insertindex);
        System.out.println(Arrays.toString(m));

    }

    @Test
    //二分查找，查找含有重复数字的数组的最左侧位置；
    public static int binarySearchLeftmost1(int[] a, int target) {
        int i = 0, j = a.length - 1;
        int candidate = -1;
        while (i <= j) {
            int m = (i + j) >>> 1;
            if (target < a[m]) {
                j = m - 1;
            } else if (target > a[m]) {
                i = m + 1;
            } else {
                candidate = m;
                j = m - 1;
            }
        }
        return candidate;
    }

    @Test
    //二分查找，查找含有重复数字的数组的最左侧位置；
    public static int binarySearchLeftmost2(int[] a, int target) {
        int i = 0, j = a.length - 1;
        while (i <= j) {
            int m = (i + j) >>> 1;
            if (target <= a[m]) {
                j = m - 1;
            } else {
                i = m + 1;
            }
        }
        return i;
    }

}
